The present invention relates to an address conversion system in a data processor for convering a virtual address of a program into a real address in a memory having the program actually located therein when the program is executed.
With progress of recent computer technology, general purpose computers of medium or large scale have frequently been equipped with so-called virtual addressing system in which the address space in the program and the address space used when a main memory is accessed by hardware are separated to facilitate program preparation. The address space for the program is called a virtual address space and the address space for addressing the main memory through hardware is called a real address space. Further, the address in the virtual address space is called a virtual address and the address in the real address space is called a real address. For the computer of the virtual address type, the program is prepared using virtual addresses. When this program is executed, the virtual address is to be converted to the corresponding real address at every main memory access. Due to its frequency, this conversion must be executed very quickly otherwise the conversion deteriorates the performance of the computer. It is the address conversion system that executes this converting function.
The correspondence between virtual and real addresses is generally tabulated in the main memory. The address conversion system, upon receipt of a virtual address, accesses the address conversion table in the main memory to convert the virtual address into the corresponding real address. A high speed memory device of small capacity is usually equipped in the address conversion system to store the correspondence between the virtual and real addresses obtained in this manner. In succeeding address conversions, the correspondence berween the virtual and real addresses is read out from the high speed memory so that the address conversion is made at extremely high speed.
In order to realize the latter function of the address conversion system, the high speed memory device is generally constructed as a kind of associative memory and called "address conversion associative memory".
The virtual and real address space is, generally speaking, partitioned into many pages, each of which has a fixed number of bytes, and the correspondence between virtual and real addresses is given on a page basis.
For this, the address conversion system is often called a paging mechanism. In this specification, "a paging circuit" will be used for signifying a circuit to convert the virtual address into the real address through accessing the address conversion table in the main memory, for ease of explanation.
The address actually obtained by the address conversion is only the upper portion of the real address and the lower portion of the real address corresponding to the address in the page is same as the corresponding portion of the virtual address. In this specification, the term "virtual address" will be used to signify either the upper part of the address notation, which is essential to the address conversion, or the whole address notation in the virtual address space, which comprises of the upper part and the lower part mentioned above. This applies also to the term "real address". The upper part of the virtual address notation mentioned above is also called the page number.
FIG. 1 shows a block diagram of one of proposed apparatus for converting the virtual address into the real address. More particularly, the apparatus shown in FIG. 1 is an address conversion system using an associative memory. Memory 1 contains virtual addresses and corresponding real address. The memory 1 holds some pairs of virtual addresses and corresponding real addresses which are used recently. When a virtual address to be converted is given, memory 1 is read to find if the virtual address is in it. The upper portion of the virtual address from the CPU is transferred to the memory 1 through a signal line 2 for obtaining a real address corresponding to the virtual address. The virtual address given from the CPU and the virtual address read out from the memory 1 are transferred to a comparator 3 for comparison. If the virtual address being now searched from the CPU is in the memory 1, the virtual address must be read out from the memory 1 accessed through the address decoder AD which decodes a part of the given virtual address. In this case, the comparator produces a coincidence signal which in turn enables a gate circuit 4 to permit the corresponding real address to be read out from a pair of virtual and real addresses stored in the memory 1. The upper part of the real address read out thus, together with the lower part of the virtual address (same as the lower part of real address) fed through the signal line 5 from the CPU, forms address information for accessing the main memory (not shown).
If the memory 1 does not include the virtual address under search from the CPU, then the memory 1 does not produce the virtual address equal to that fed from the CPU. In this case, the comparator 3 produces a non-coincidence signal to be directed to a control circuit 6. The control circuit, upon receipt of the non-coincidence signal, operates so as to access the main memory, which stores all of the correspondence relationships (corresponding to a known page table) between the virtual addresses and the real addresses. Through this access, the real address corresponding to the virtual address searched from the CPU is read out from the main memory and the virtual and real addresses are loaded into the memory 1. The details of the address conversion referring to the main memory are not described because the conversion using the table in the main memory is not essential to the present invention.
In the above explanation referring to FIG. 1, the number of the virtual and real addresses read out from the memory 1 are each single, for simplicity. In actuality, however, when a virtual address is applied to the memory 1, a plurality (for example, four) of virtual addresses and a plurality of real addresses corresponding to them are read out from the memory 1. Similarly, a plurality of comparators 3 are used to compare a plurality of virtual address read out and the virtual address fed through the line 2. The real address corresponding to the virtual address which is coincident with the given real address is outputted through the gate circuit 4. This is called a set associative system, and is described in detail below.
FIG. 2 shows a block diagram of a more detailed circuit construction of FIG. 1. In FIG. 2, a virtual address as an address control word from the CPU (not shown) is stored in a register 10. In this example, the virtual address stored in the register 10 consists of 0th through 35th bits, and the upper part (0th through 23th bits) of it is to be replaced by the upper part of the corresponding real address. A part (for example, 20th through 23rd bits) of the upper part of the virtual address is used to address memories 11 and 12, each of which has four identical compartments of 16 words each, giving so-called 16.times.4 logical configuration. Each of the compartments consist of several memory elements of 4 bits.times.16 words configuration. The memory 11 stores the virtual address and the memory 12 stores the real address corresponding to the virtual address. In the drawing, these memories are illustrated as separate entites: however, these memories may be considered as a single memory for storing the address information including the pairs of real and virtual addresses. In response to the address information, address decoders 13 and 14 access the memories 11 and 12, respectively. Another part, e.g. 0th through 19th bits, of the upper part of the given virtual address is transferred to the comparators 15 to 18 to be compared with the virtual addresses read out from memory 11. If one of the comparators 15 to 18 exhibits a coincidence between the virtual addresses, it is called hit state. This state of hit indicates that the memory 11 stores the virtual address equal to that of the address control word in the register 10. The output signals of the comparators 15 to 18 serve as enable signals to the memory 12 storing the corresponding real addresses. That is, when one of the comparators 15 to 18 produces the coincidence (hit) signal, the corresponding memory 12 is enabled to give the real address corresponding to the coincided virtual address. The output of the memory 12 is applied via OR circuits 19 to the signal lines 20. For addressing the main memory, the real address read out and a part, e.g. 24th through 35th bits, of the virtual address transferred from the CPU are coupled and loaded into the address register (not shown) of the main memory. A selector 21 selects the addresses transferred through the signal lines 20 bearing the real address and signal lines 22 bearing a part of the virtual address and transfers them into the address register of the main memory. As will be described later, the selector 21 may select the address from a paging circuit 26 in other cases.
When none of the comparators 15 to 18 produces an output, i.e. in a nonhit state, the memory 11 storing the virtual addresses does not store the virtual address equal to that of the address control word stored in the register 10. Accordingly, the memory 12 does not have the corresponding real address. Therefore, it is impossible to access the main memory. In this state of nonhit, it is necessary to access the address conversion table in the main memory and to read out the real address corresponding to that virtual address. For this, the nonhit signal from the comparators 15 to 18 are transferred to a control circuit 24 through an AND circuit 23. That is, if the control circiut 24 receives the nonhit signal through the AND circuit 23, it judges occurrence of the nonhit in the comparators 15 to 18. Upon the nonhit condition, the control circuit 24 commands to read out the corresponding portion of the address conversion table in the main memory to a paging circuit 26, through control lines 25. The upper part, e.g. 0th through 23rd bits, of the virtual address to be converted is applied through a signal line 29 to the paging circuit 26, where predetermined address calculation is performed on the basis of this part of the address to produce the corresponding address of the page conversion table. The address is transferred to the main memory via signal lines 32 and the selector 21 to retrieve the data stored therein. Since the address calculation is not essential to the present invention, the description thereof will be omitted. This calculation and data retrieval may have to be repeated one or more times (depending on the construction of the address conversion table) to read out data including the real address corresponding to the given virtual address.
Data read out from the main memory are transferred to the paging circuit 26 via signal lines 28, and the real address is loaded into the memory 12 via signal lines 30. The virtual address in the virtual address register 10 is loaded into the memory 11 by way of the signal lines 33. The loading of the real and virtual addresses into the memories 11 and 12 is controlled by a round robin counter (not shown) for specifying the compartment of the memories 11 and 12 to which these addresses are loaded. Signal lines 27 are used to transfer write data to the main memory, when the address conversion table in the main memory is to be updated. The read data other than the above-mentioned real address information are transferred through control lines 31 to the control circuit 24 for execution of desired control. A part of the other control data (for example, "written bit" of that control data) is written into the memory 12, together with the real address. The details of this will be omitted in description since it is not essential to the present invention.
The address conversion system of the above-mentioned conventional associative memory system by one level suffers from the following disadvantages.
One of the disadvantages is that the address conversion time from application of the virtual address to production of the real address necessarily includes the access time of the memory 1, even if the address conversion associative memory is hit, i.e. even if the time required for the address conversion is minimum. The access time of the memory 1 is generally several to several tens of ns but this is large enough to be significant in a reference clock period (e.g. 300 ns, 100 ns or so). The address conversion system may frequently be located on a signal path which is a critical path for reducing the reference clock period. Therefore, the access time of the memory 1 is one of factors defining the upper limit of the reference clock period of a computer. If the access time of the memory 1 is not included in the address conversion time, the clock period of the computer may be reduced by the access time so that the entire processing time of the computer is possibly improved ten to twenty percent.
Another disadvantage of the conventional address conversion system is that it needs memory elements having a proper scale of integration (for example, 4 bits.times.16 words). The problem is not serious when technology with a large number of IC families is used. However, when technology with a small number of IC families, for example, only two kinds of memory elements 4 bits.times.4 words and 2 bits.times.128 words, are available, the address conversion system realized using them is expensive and of poor performance. For example, when the memory of 16 words as shown in FIG. 2 is to be constructed by using memory elements of 4 bits.times.4 words, four chips are needed in the word direction so that the chip number of the entire unit is four times. This leads to an expensive and bulky address conversion system and also to elongation of the signal transfer delay.
Alternatively, when 2 bits.times.128 words memory is used, the access time is elongnated because of the long access time of the memory element which has an unnecessarily large capacity. Accordingly, the time required for the address conversion and thus the reference clock period of the entire computer are elongated, resulting in deterioration of the computer performance.